from typing import List

class Solution:
    def trap_dp(self, height: List[int]) -> int:
        """
        动态规划解法
        时间复杂度：O(n)
        空间复杂度：O(n)
        """
        if not height:
            return 0
            
        n = len(height)
        left_max = [0] * n
        right_max = [0] * n
        
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(height[i], left_max[i-1])
            
        right_max[n-1] = height[n-1]
        for i in range(n-2, -1, -1):
            right_max[i] = max(height[i], right_max[i+1])
            
        water = 0
        for i in range(n):
            water += min(left_max[i], right_max[i]) - height[i]
            
        return water

    def trap_two_pointers(self, height: List[int]) -> int:
        """
        双指针解法
        时间复杂度：O(n)
        空间复杂度：O(1)
        """
        if not height:
            return 0
            
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        water = 0
        
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    water += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    water += right_max - height[right]
                right -= 1
                
        return water

    def trap_stack(self, height: List[int]) -> int:
        """
        单调栈解法
        时间复杂度：O(n)
        空间复杂度：O(n)
        """
        if not height:
            return 0
            
        stack = []
        water = 0
        
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                distance = i - stack[-1] - 1
                bounded_height = min(height[i], height[stack[-1]]) - height[top]
                water += distance * bounded_height
            stack.append(i)
            
        return water 